1. Technical Field
The present invention relates generally to an improved data processing system and in particular to a system and method for an optimized least recently used lookup cache. Still more particularly, the present invention provides a system and method for a least recently used lookup cache having reduced updates.
2. Description of Related Art
A set associative cache allows data from any address to be stored in a cache location. The cache address is used as a tag. All tags maintained by the cache must be compared with a requested address. If a tag matches the requested address, the matching tag's associated data is then accessed. A set associative cache requires an associative memory to hold the tags. A set associative cache separates objects to be cached into sets based on a unique identifier and every object will belong to one set only. As objects are added to the cache, each set can only grow to a limited size. Once the set has reached its full size, an existing object must be discarded each time a new object is added. Typically, the discarded object will be the least recently used (LRU) object in the set.
A name lookup cache is derived from the general set associative cache architecture. Because a name lookup cache generally contains only a subset of all existing objects in a system, as objects are added to the cache, each set can only grow to a limited size. Once the set has reached its full size, an existing object—typically the least recently used object—must be discarded every time a new object is added. Typically, the set is a linked list that is searched in a linear fashion starting at the head. The search ends when the object is found or the tail object is searched. If the object was found, it is moved from its current position in the list to the head of the list to implement an LRU algorithm. In the way, the most frequently accessed objects will tend to migrate toward the head of the list while the least recently used objects will be sifted toward the tail and ultimately be discarded from the list.
The present invention recognizes that the above-described name lookup cache and LRU implementation exhibits serious performance problems on modern large symmetric multiprocessor computers. Particularly, the LRU algorithm is implemented by moving objects to the head of the cache list and, thus, for every cache hit or insertion of a new object, the set's list anchor must be modified to point to the new list head object. Due to various characteristics of modern memory design, global data that is frequently modified presents a serious performance inhibition in a name lookup cache organized by an LRU algorithm.
Thus, it would be advantageous to provide an optimized look-up cache. It would be further advantageous to provide a look-up cache having an optimized LRU functionality. It would still be further advantageous to provide a look-up cache requiring less frequent updates to the list of cached objects compared to conventional lookup cache implementations.